package com.base.dataStructure.priorityqueue;

import com.base.dataStructure.queue.Queue;

/**
 * @Author: hdhao
 * @Create: 2023/4/2 - 17:44
 * @Version: v1.0
 */
//基于大顶堆实现的优先级队列
//优先级队列:一端进,一端出 按优先级出队
@SuppressWarnings("all")
public class PriorityQueue3<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;//数组中元素个数的大小,也可以把它当做尾指针

    public PriorityQueue3(int capacity) {
        this.array = new Priority[capacity];
    }

    /*
        1、入堆新元素，加入到数组末尾(索引位置child)
        2、不断比较新加元素与它父节点(parent)的优先级
            -如果父节点优先级低,则向下移动,并找到下一个parent
            -直至父节点优先级更高或child == 0 为止
     */
    @Override
    public boolean offer(E offered) {
        if(isFull()){
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && offered.priority() > array[parent].priority()) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = offered;
        return true;
    }
    /*
        1、交换堆顶和尾部元素,让尾部元素出队
        2、(下潜)
            -从堆顶开始,将父元素与两个孩子较大者交换
            -直到父元素大于两个孩子,或没有孩子为止
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0,size - 1);
        size--;
        Priority e = array[size];
        array[size] = null;//help GC

        down(0);
        return (E) e;
    }
    private void down(int parent) {
        int left = 2 * (parent + 1);
        int right = left + 1;
        int max = parent;//假设父元素的优先级最高
        if (left < size && array[left].priority() > array[max].priority()){
            max = left;
        }
        if (right < size && array[right].priority() > array[max].priority()){
            max = right;
        }
        if (max != parent){ //发现了有子元素比父元素大
            swap(max,parent);
            down(max);
        }
    }
    private void swap(int i, int j) {
        Priority t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
